//
//  main.cpp
//  26.删除有序数组中的重复项1
//
//  Created by Yan Zihao on 2024/10/8.
//

#include <iostream>
#include<vector>
using namespace std;

class Solution
{
public:
    int removeDuplicates(vector<int>& nums)
    {
        int n = nums.size();
        if (n == 0)
        {
            return 0;
        }
        int fast = 1, slow = 1;
        while (fast < n)
        {
            if (nums[fast] != nums[fast - 1])
            {
                nums[slow] = nums[fast];
                ++slow;
            }
            ++fast;
        }
        return slow;
    }
};


/*方法一:使用erase删除重复数据，不过会导致数据挪动，时间复杂度为O(N*N)
*思路：
* 1. 由于数据是排序好的，通过查询每一个数据的重复区间
* 2. 将重复区间进行删除，只保留一个数据即可
*/
class Solution {
public:
  int removeDuplicates(vector<int>& nums)
  {
    if(nums.size() == 1)
      return 1;
    vector<int>::iterator it = nums.begin();
    vector<int>::iterator it1 = it;
    it1++;

    while(it != nums.end())
    {
      while(it1!=nums.end() && *it1==*it)
        it1++;
      it = nums.erase(++it, it1);
      it1 = it;
      it1++;
    }
    return nums.size();
  }
};

/*方二:时间复杂度为O(N)
*思路：
* 1. 由于数据是排序好的，通过查询每一个数据的重复区间
* 2. 将重复区间进行删除，只保留一个数据即可
*/
int removeDuplicates(int* nums, int numsSize)
{
  int src1 = 0, src2 = 1;
  int dst = 0;
  // 跟上题的思路一致，相同的数只保留一个，依次往前放
  while(src2 < numsSize)
  {
    nums[dst] = nums[src1];
    ++dst;
        //如果两个指针指向的元素不重复，则指针同时向后移动
    if(nums[src1] != nums[src2])
    {
      ++src1;
      ++src2;
    }
    else
    {
      //如果重复，找到第一个不重复的元素
      while(src2 < numsSize && nums[src1] == nums[src2])
      {
        ++src2;
      }
      //更新指针
      src1 = src2;
      ++src2;
    }
  }
  if(src1 < numsSize)
  {
      nums[dst] = nums[src1];
      ++dst;
  }
  return dst;
}

